An optimization approach to locally-biased graph algorithms

摘要

Locally-biased graph algorithms are algorithms that attempt to find local orsmall-scale structure in a large data graph. In some cases, this can beaccomplished by adding some sort of locality constraint and calling atraditional graph algorithm; but more interesting are locally-biased graphalgorithms that compute answers by running a procedure that does not even lookat most of the input graph. This corresponds more closely to what practitionersfrom various data science domains do, but it does not correspond well with theway that algorithmic and statistical theory is typically formulated. Recentwork from several research communities has focused on developing locally-biasedgraph algorithms that come with strong complementary algorithmic andstatistical theory and that are useful in practice in downstream data scienceapplications. We provide a review and overview of this work, highlightingcommonalities between seemingly-different approaches, and highlightingpromising directions for future work.